package solution3;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        // Instead of using a set to tell if a character exists or not,
        // we could define a mapping of the characters to its index.
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for (int i=0, j=0; i<s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                // skip all the elements in the range [i, j'],
                // let i to be j'+1 directly
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }

    // the same
    public int lengthOfLongestSubstring2(String s) {
        int n = s.length();
        int ans = 0;
        // Instead of using a set to tell if a character exists or not,
        // we could define a mapping of the characters to its index.
        Map<Character, Integer> map = new HashMap<>();
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(map.get(s.charAt(j)))) {
                i = Math.max(i, map.get(s.charAt(j)));
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j),j+1);
        }
        return ans;
    }

    // not better
    // Time complexity: O(2n) = O(n)
    // Space complexity: O(min(m,n).
    public int lengthOfLongestSubstring3(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0;
        int i = 0, j = 0;
        while (i < n && j < n) {
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }

    //If we know that the charset is rather small, we can replace the Map with an integer array as direct access table.
    //Commonly used tables are:
    //int[26] for Letters 'a' - 'z' or 'A' - 'Z'
    //int[128] for ASCII
    //int[256] for Extended ASCII
    public int lengthOfLongestSubstring4(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            // 关键语句
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}
